For a variety of applications, it is desired to be able to pass messages or tokenized information between multiple parties, such as a virtual deck of cards, e-voting, secure circuit evaluation schemes, and other forms of information sharing over an insecure, peer-to-peer, or broadcast medium, where the information must only be made available to specific individuals under specific constraints. A body of prior art is directed to this problem, and is commonly termed “Mental Poker” (MP), in light of the particular problems posed by Poker and other card games, particularly if gambling or the exchange of money is to take place.
To execute an MP protocol, players are required to do computations. In order to achieve acceptable security, these computations involve large numbers, are very hard to do by hand, and are almost impossible to do mentally, so each player relies on a programmed computer device that compute on his behalf. This device not only performs computations on behalf of the player, but validates the other players' computations in order to detect cheating. Each device in this protocol is termed an “agent”.
MP protocols can be divided into two main groups: protocols that require a trusted third party (TTP) and protocols that do not (TTP-Free). In the former there is a third party who draws and knowns the cards in each player's hand, so it is necessary that the third part is trustworthy and impartial. From the point of view of a poker player, an e-gaming site that uses an MP protocol with TTP still poses a security risk. In TTP-free protocols, only each player knows his own hand of cards, and the site operator is not able to know any player's cards. In the context of a voting scheme, a protocol with TTP means that a central private or governmental office, or a collusion of offices, could recover enough information to trace each vote to its voter, and therefore only a TTP-free protocol can provide true anonymity and adequate security for individual voters.
Reference numbers in brackets, used throughout this specification, refer to the Bibliography that follows this Background Section. All references in the Bibliography are incorporated herein by reference.
Shamir, Rivest and Adleman proposed the first TTP-Free protocol [SRA81] that achieved some of the properties desired for card games, but forced the players to reveal their hands and their strategy at the end of the game. In [Cr86], a set of requirements for an MP protocol were established, whereby if a protocol satisfied the set, the protocol would be deemed to be as secure as a “real” card game, with participants mutually present. [Cr86] also presented the first protocol that purported to satisfy the set of requirements. However the protocol is not practical, since an implementation is reported to take 8 hours to shuffle a poker deck [E94]. Other protocols were later developed [KKO90][BS03][CDRB03][CR05], but were excessively complex, making them difficult to verify, extend, or implement.
The art described in this section is not intended to constitute an admission that any patent, publication or other information referred to herein is “prior art” with respect to this invention, unless specifically designated as such. In addition, this section should not be construed to mean that a search has been made or that no other pertinent information as defined in 37 CFR §1.56(a) exists.